A Mobile Ad-Hoc Network (MANET) is a wireless network in which the nodes can freely and dynamically self-organize into arbitrary and temporary network topologies, allowing people and devices to seamlessly internetwork in areas without a central coordination or a pre-established communication infrastructure.
In such networks, the address assignment to mobile devices is one of the most important network configuration parameters. In practice, no mobile device can participate in any form of communication until it is assigned an address. Furthermore, the majority of the routing protocols assume that mobile nodes in ad hoc networks are configured a priori with unique address identifiers before they gain access to the network. However, the pre-configuration of a static address is not always possible and has some drawbacks. The use of traditional IP-based address assignment schemes, such as DHCP, is not feasible because nodes in a MANET environment are highly mobile and a permanent central infrastructure component is not always reachable to any node. In addition, due to possible frequent node mobility from one network to another, other address issues need to be handled like duplicate address detection, abrupt disconnections, network partitioning, and merging. Accordingly, an auto-configuration scheme is essential to building self-organized network systems.
Several auto-configuration schemes have previously been proposed for MANETs. They could be classified as stateful or stateless approaches according to the management of the address space. For stateful approaches, the state of each node is held in such a way the network has a vision of assigned and non assigned addresses. Stateless approaches do not have a network view, and each node chooses its own address.
The stateless approaches are all decentralized and use some self-configuration address allocation method in which a node can configure itself using a combination of locally available information such as its hardware address, a pre-assigned UUID (Universally Unique Identifier) [S. Cheshire, B. Aboba, and E. Guttman, Dynamic Configuration of IPv4 Link-Local Addresses, draft-ietfzeroconf-ipv4-linklocal-17.txt, IETF Zeroconf Working Group, July 2004][S. Thomson and T. Narten, IPv6 Stateless Address Autoconfiguration, RFC 2462, December 1998], or even a random number [C. E. Perkins, J. T. Malinen, R. Wakikawa, E. M. Belding-Royer, and Y. Sun, IP Address Autoconfiguration for Ad Hoc Networks, draft-ietfmanet-autoconf-01.txt, IETF MANET Working Group, July 2000]. For this reason, the stateless approaches almost always make use of a mechanism for Duplicate Address Detection (DAD) to resolve address conflicts, and so, ensure address uniqueness over the network. There are at least three common types for DAD: Strong DAD (SDAD) [N. Vaidya, “Weak Duplicate Address Detection in Mobile Ad Hoc Networks”, In Proc.ACM MobiHoc 2002, June 2002], Weak DAD (WDAD) [N. Vaidya, supra], and Passive DAD (PDAD) [K. Weniger, “Passive Duplicate Address Detection in Mobile Ad Hoc Networks”, In Proc.IEEE WCNC 2003, March 2003].
Strong DAD uses the metrics hop count and the DAD control message timer in order to deal with the problem of address duplication in MANET. In this technique, a node checks if a randomly chosen address is already in use by querying other nodes of the network. Based on a reply for the claimed request, which needs to arrive at the node within a finite bounded time interval, the node can detect address duplication in the network [N. Vaidya, supra]. However, the strong DAD may not detect a duplicate address of a node out the range of the hop-count (or TTL) of the DAD control message, so as a result the weak DAD has been proposed [N. Vaidya, supra].
The weak DAD [N. Vaidya, supra] and the passive DAD [K. Weniger, supra] can be designated as routing-based DAD since they use the routing protocol packet format to detect address conflicts including those that can arise after MANETs merger. In WDAD, a key is added to the routing control message, which can be chosen either randomly or based on a universally unique ID. This way, a node can figure out address conflicts when there are two messages with the same source address and distinct interfaces keys. The passive DAD can detect address duplication by using the sequence number of the routing control message and without using the additional information such as the interface key [Y. Kim, S. Ahn, Y. Lee, J. Jeong and J. Lee, “Design and Implementation of IPv6 Address Autoconfiguration for AODV in Mobile Ad Hoc Networks”, The 2005 US-Korea Conference on Science, Technology & Entrepreneurship (UKC 2005), University of California at Irvine, Aug. 11-13, 2005].
In the stateful autoconfiguration approaches, nodes obtain addresses, other configuration information or both from one or more servers. Servers maintain a database that keeps track of which addresses have been assigned to which hosts. There are several stateful solutions that can differ in how and what information is kept. Such solutions can be divided into four sub-categories depending on their use of: a centralized allocation table, a distributed allocation table, distributed disjoint tables, and a distributed allocation function.
Centralized allocation table solutions are usually used in fixed networks since in MANETs it is often difficult to maintain a single centralized structure. In this approach a server acts as a centralized address pool of available addresses. When a node requires an address, it then sends a request and the server replies with a message which contains the address that was assigned to the requesting node. DHCP [R. Droms. Dynamic Host Configuration Protocol. IETF Network Working group—RFC2131, March 1997] is a good and well-known example of this approach.
Distributed allocation table solutions do not have a centralized structure, instead, they have a table that is maintained in a distributed way, where every node has a copy of such table, and messages are used to maintain the consistency of all tables. MANETconf [S. Nesargi and R. Prakash, MANETconf: Configuration of Hosts in a Mobile Ad Hoc Network, INFOCOM 2002] proposed a solution that makes all hosts record addresses already allocated. In MANETconf, a node that wants an address, must find a neighbour and request the address to it. The neighbour looks into its table and chooses an address that is not allocated, or a free address. After choosing a free address, the neighbour asks all other nodes for confirmation, to ensure that the selected address is really free. In the case that the address is really not in use, it will then be assigned to the new (requesting) node.
Distributed disjoint tables solutions are different from the previous presented table based solutions because the maintained tables are different between nodes. In [A. Tayal and Patnaik L., “An Address Assignment for the Automatic Configuration of Mobile Ad hoc Networks”, Personal Ubiquitous Computing, 2004], a method for address allocation that uses the concept of binary split is presented. In the proposed method, a new node that is willing to join the MANET has to contact an existing one. The previously configured node, takes it address pool, divides it into two parts and gives one half to the requesting node. In the event that the requesting node does not have an address pool, it starts searching for nodes that might have it. In the proposed method, every node has a disjoint address pool that it can use to assign addresses to a new node without consulting any other one in the network, except the case where it needs to forward the request.
Distributed allocation function based solutions are different from all previous stateful solutions introduced so far. They do not use an address allocation table. The address allocation methods used in this class of approaches, establish that each node uses a generation function and maintains a state value, in order to generate a disjoint set of addresses. Examples of solutions that make use of methods like these are: Prophet Address Allocation [H. Zhou, L. M. Ni, and M. W. Mutka, Prophet Address Allocation for Large Scale MANETs, INFOCOM 2003], and Prime Numbering Address Allocation (PNAA) [Y.-Y. Hsu and C.-C. Tseng. Prime DHCP: A Prime Numbering Address Allocation Mechanism for MANETs. IEEE Communication Letters, 9(8), August 2005].
Prophet is a solution that supports partition and merges MANET operations through an advanced address management mechanism. Prophet's address allocation method generates, with a high probability, a unique sequence of addresses. The efficiency of the proposed method depends on the address space, where the bigger the address space used, the less likely of a conflict occurring. Although address duplication may still happen in Prophet, it can nonetheless be predicted.
The PNAA approach eliminates address conflicts to ensure precisely a unique sequence of addresses for each node. This method stems from the mathematical definition that every positive number can be written as a product of prime numbers in a unique way. PNAA states that the first node that creates a network is the root node and has address 1 (one). The root node allocates all prime numbers in sequence to new nodes. Non-root nodes allocate addresses as their own address multiplied by a prime number which starts from the biggest prime factor of its own address.
The present applicant has appreciated the following problems with the existing solutions.
A major drawback of stateless solutions is the need to confirm and check address uniqueness through DAD techniques, usually, by flooding the entire network. This introduces a large and unnecessary overhead. The solutions that use hardware addresses also suffer from privacy problems, because they tend to generate the same addresses and can easily be tracked [T. Narten, R. Draves, Privacy Extensions for Stateless Address Autoconfiguration in IPv6, RFC3041 January 2001].
Centralized allocation table solutions do not fit well into MANETs due to their dynamic nature. These solutions only work when the allocation server never gets disconnected from the network. Moreover, as nodes that do not have direct access to the server need to use intermediary nodes, a small additional overhead is introduced. Its level depends on the network topology and some nodes can get their resources exhausted by forwarding messages to the server.
Distributed allocation table solutions solve the problems that arise from a centralized server, but introduce a new one, namely, the need to maintain, in a distributed way, the consistency of the allocation table.
Although MANETconf, for example, guarantees address uniqueness, the table synchronization method is complex and the address assignment process uses network flooding, hence consuming network bandwidth. The solution could also generate a high delay because, before a node can allocate an address, it needs to ask all the other network nodes for permission to do so.
Distributed disjoint tables solutions are a good alternative that minimizes such additional traffic, but the allocation function needs to be suitably designed to guaranty the generation of unique addresses.
The Prophet solution is very easy to implement, but it cannot find a function that generates no address duplication, and is only applicable to large address space MANETs.
PNAA introduces a conflictless number generator, that is easy to understand but its address space utilization is not optimized since it is not well distributed among non-root nodes. Network partition and merge operations are also supported but the idea introduced to accomplish this goal could be optimized. The method used to deal with abrupt node departure tries to recover addresses as early as possible, which is not good in a high mobile environment, in which nodes may go off range frequently, also partitions are formed an merged back, and can cause too much overhead in the case of a previous address recovery.